In the process of data storing and transmission, the factors such as linear noise, out-of-sync in the demodulation process, deep fading and multi-path propagation in the wireless transmission, and track defect in the magnetic storage give rise to strings of paroxysmal transmission errors, which are called “bursts”. A burst whose length is l may be defined as a vector, and its non-0 elements are limited to l continuous positions. Generally, bits designed to correct random errors are inefficient in correcting bursts. Therefore, research for burst correction codes are very important, and burst correction codes have been widely applied to the communication system and the storage system.
There is a method for correcting burst errors in the prior art. In the method, a code with a correction capability “l” can correct bursts whose length is l or shorter, but cannot correct the bursts whose length is l+1. Such a correction mode is known as Deterministic Burst Correction (DBC). The highest correction capability of a DBC can be calculated according to a formula of [(n−k)/2] (n is length of correction codes of the DBC, k is information length of correction codes of the DBC), the upper limit of the correction capability of the DBC is known as “Reiger Bound”. There is another burst correction way in the prior art, known as “Probabilistic Burst Correction” (PBC), by using which, longer bursts can be corrected at a high probability. Thus, the PBC is more powerful than the DBC, and is very promising burst correction method.
Cyclic codes are an important subtype of linear block code, and are most frequently applied to the engineering. Cyclic shift of each codeword of a cyclic code is still a codeword of the code. Due to cyclic characteristics of cyclic codes, the cyclic codes can be encoded by a generation polynomial serving as a feedback shift register of a feedback coefficient, or by multiplication of a generation matrix and an information vector; the corrector of the decoder may be calculated out by a check polynomial serving as a feedback shift register of a feedback coefficient, or by multiplication of a check matrix and a codeword vector. Because cyclic codes have a rigorous algebraic structure, the cyclic codes may be decoded in many methods, for example, error-trapping decoding algorithm, majority-logic decoding algorithm, trellis decoding algorithm of linear block codes, broad-sense minimum distance decoding algorithm, Chase decoding algorithm, and maximum-likelihood decoding algorithm. Cyclic decoding is widely applied to error control of the communication system, and is especially effective in error detection.
Currently, the PBC method of linear codes provides only an ideal approach to probabilistic burst correction of linear codes, but does not provide specific implementation method or detailed decoding process intended for a specific code type such as cyclic codes or Low Density Parity Check (LDPC) codes.